package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//递归:16ms 82%, 6.9MB 96%
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if (p.Val <= root.Val && root.Val <= q.Val) || (q.Val <= root.Val && root.Val <= p.Val) {
		return root
	}
	if root.Val > q.Val {
		return lowestCommonAncestor(root.Left, p, q)
	} else {
		return lowestCommonAncestor(root.Right, p, q)
	}
}

func main() {
	fmt.Println(lowestCommonAncestor(&TreeNode{
		2,
		&TreeNode{1, nil, nil},
		&TreeNode{3, nil, nil},
	},
		&TreeNode{2, nil, nil},
		&TreeNode{3, nil, nil}))
}
